package stu.edu.InterviewQuestion;

import java.util.HashMap;
import java.util.Map;

public class ComplexListClone {

    public static void main(String[] args) {
        RandomListNode root = new RandomListNode(1);

        root.next = new RandomListNode(2);
        root.random = new RandomListNode(3);
        RandomListNode result = Clone(root);
        System.out.println(result);
    }

    public static RandomListNode Clone(RandomListNode pHead){
        RandomListNode root = null;
        Map<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode originRoot = pHead;
        RandomListNode result = null;
        while(pHead != null) {
            if(root == null) {
                root = new RandomListNode(pHead.label);
            }else {
                root.next = new RandomListNode(pHead.label);
                root = root.next;
            }
            if(map.size() == 0) {
                result = root;
            }
            map.put(pHead,root);
            pHead = pHead.next;
        }
        while(originRoot != null) {
            RandomListNode newLy = map.get(originRoot);
            if(originRoot.random != null) {
                newLy.random = new RandomListNode(originRoot.random.label);
            }
            originRoot = originRoot.next;
        }
        return result;
    }

    private static class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }

}
